package com.demo.uitls;

/**
 * 队列实现方式：顺序（数组）、链式（链表）
 * <p>
 * 为充分利用向量空间，克服【顺序存储结构】的"假溢出"现象的方法是：将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。
 * 存储在其中的队列称为循环队列（Circular Queue）。
 * 这种循环队列可以以单链表的方式来在实际编程应用中来实现。
 * <p>
 * 循环队列中，由于入队时尾指针向前追赶头指针；出队时头指针向前追赶尾指针，造成队空和队满时头尾指针均相等。
 * 因此，无法通过条件front==rear来判别队列是"空"还是"满"。使用求余运算可以判断队列是否已满。
 *
 * @Author DongXL
 * @Create 2018-06-26 10:20
 */
public class CircularQueue<E> {

    /**
     * 循环队列 （数组）默认大小
     */
    private static final int DEFAULT_SIZE = 1000;

    private static final Object[] EMPTY_ELEMENTDATA = {};

    /**
     * 队头(先进先出)
     */
    private int front;
    /**
     * 队尾
     */
    private int rear;
    /**
     * (循环队列)数组的容量
     */
    private int capacity;

    /**
     * 数组：保存循环队列的元素
     */
    transient Object[] elementData;

    /**
     * 以循环队列 默认大小创建空循环队列
     */
    public CircularQueue() {
        this.capacity = DEFAULT_SIZE;
        this.elementData = new Object[DEFAULT_SIZE];
    }

    /**
     * 以指定长度的数组来创建循环队列
     *
     * @param initialCapacity
     */
    public CircularQueue(int initialCapacity) {
        if (initialCapacity > 0) {
            this.capacity = initialCapacity;
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: " +
                    initialCapacity);
        }
    }

    /**
     * 队列为空
     *
     * @return
     */
    public boolean isEmpty() {
        return front == rear;
    }

    /**
     * 对列满
     *
     * @return
     */
    public boolean isFull() {
        return front == (rear + 1) % capacity;
    }

    /**
     * 获取循环队列的大小(包含元素的个数)
     *
     * @return
     */
    public int size() {
        return (rear - front + capacity) % capacity;
    }

    /**
     * 入队
     * @param e
     * @return
     */
    public boolean enQueue(E e) {
        if (isFull()) {
            return false;
        }
        elementData[rear] = e;
        rear = (rear + 1) % capacity;
        return true;
    }

    /**
     * 出队
     * @return
     */
    public E deQueue() {
        if (isEmpty()) {
            return null;
        }
        E e = (E) elementData[front];
        front = (front + 1) % capacity;
        return e;
    }

    @Override
    public String toString() {
        if (isEmpty()) {
            return "[]";
        } else {
            StringBuilder sb = new StringBuilder("[");
            int i = front;
            while ((i % capacity) != rear) {
                sb.append(elementData[i] + ",");
                i = (i + 1) % capacity;
            }
            sb.deleteCharAt(sb.length() - 1).append("]");
            return sb.toString();
        }
    }

    public static void main(String[] args) {
        CircularQueue<Integer> queue = new CircularQueue<>(3);
        queue.enQueue(31);
        queue.enQueue(32);
        System.out.println(queue);
        System.out.println(queue.deQueue());
        System.out.println(queue);

    }

}
